
#include <iostream>
#include <stdexcept>
using namespace std;


// Linked list
template<typename T> class list{
public:
	// Default construction
	list() : m_head(NULL), m_tail(NULL) {}
	// Copy construction
	list( list const& that ) : m_head(NULL), m_tail(NULL){
		for(node* pnode = that.m_head; pnode; pnode = pnode->m_next)
			push_back(pnode->m_data);
	}
	// Destructor
	~list(){
		clear();
	}
	// Linked list is full ?
	bool empty(){
		return m_head == NULL && m_tail == NULL;
	}
	// Insert  front node
	void push_front(T const& data){
		m_head = new node(NULL, data, m_head);
		if(m_head->m_next)
			m_head->m_next->m_prev = m_head;
		else
			m_tail = m_head;
	}
	// Delete front node
	void pop_front(){
		if(empty())
			return;
		node* pnode = m_head->m_next;
		delete m_head;
		m_head = pnode;
		if(m_head)
			m_head->m_prev = NULL;
		else
			m_tail = NULL;
	}
	// Insert rear node
	void push_back(T const& data){
		m_tail = new node(m_tail, data, NULL);
		if(m_tail->m_prev)
			m_tail->m_prev->m_next = m_tail;
		else
			m_head = m_tail;
	}
	// Delete rear node
	void pop_back(){
		if(empty())
			return;
		node* pnode = m_tail->m_prev;
		delete m_tail;
		m_tail = pnode;
		if(m_tail)
			m_tail->m_next = NULL;
		else
			m_head = NULL;
	}
	// Get front data
	T& front(){
		if(empty())
			throw underflow_error("front(): NULL list");
		return m_head->m_data;
	}
	T const& front()const{
		return const_cast<list*>(this)->front();
	}
	// Get rear data
	T& back(){
		if(empty())
			throw overflow_error("back(): NULL list");
		return m_tail->m_data;
	}
	T const& back()const{
		return const_cast<list*>(this)->back();
	}
	// Clear the link list
	void clear(){
		while(!empty())
			pop_front();
	}
	// Get link list size
	size_t size(){
		size_t i = 0;
		for(node* pnode = m_head; pnode; pnode = pnode->m_next)
			++i;
		return i;
	}

private:
	class node{
	public:
		node(node* prev, T data, node* next) : m_prev(prev), m_data(data), m_next(next){}

		node* m_prev;	// Front pointer
		T m_data;	// Data
		node* m_next;	// Rear pointer
	};
public:
	// Forward direction iterator
	class iterator{
	public:
		iterator(node* start, node* cur, node* end)
			: m_start(start), m_cur(cur), m_end(end){}
		T& operator*(){
			if(m_cur == NULL)
				throw underflow_error("operator* : NULL node");
			return m_cur->m_data;
		}
		iterator& operator++(){
			if(m_cur == NULL)
				m_cur = m_start;
			else
				m_cur = m_cur->m_next;
			return *this;
		}
		iterator& operator--(){
			if(m_cur == NULL)
				m_cur = m_end;
			else
				m_cur = m_cur->m_prev;
			return *this;
		}
		bool operator==(iterator const& that)const{
			return m_start == that.m_start && m_cur == that.m_cur && m_end == that.m_end;
		}
		bool operator!=(iterator const& that)const{
			return !(*this==that);
		}
	private:
		node* m_start;
		node* m_cur;
		node* m_end;
	};
	iterator begin(){
		return iterator(m_head, m_head, m_tail);
	}
	iterator end(){
		return iterator(m_head, NULL, m_tail);
	}

private:
	node* m_head;	// Head
	node* m_tail;	// Tail

//	friend ostream& operator<<(ostream& os, list<int>& l);
};

// ----------------------------------------------------------------------------------


/*
ostream& operator<<(ostream& os, list<int>& l){
	for(list<int>::node* pnode = l.m_head; pnode; pnode = pnode->m_next)
		os << pnode->m_data << ' ';
	return os;
}
*/


void print(string const& str, list<int> l){
	cout << str << endl;
	typedef list<int>::iterator IT;
	for(IT it = l.begin(); it != l.end(); ++it)
		cout << *it << ' ';
	cout << endl << "---------------------------------------" << endl;
}

int main(){
	list<int> ls;
	for(int i = 0; i < 5; ++i )
		ls.push_front(i+10);
	for(int i = 0; i < 5; ++i )
		ls.push_back(i+100);
	print("Before", ls);

	ls.pop_front();
	ls.pop_back();

	print("After", ls);
	
	return 0;
}

